package code.starivan.leetcode;

import com.sun.javafx.fxml.expression.KeyPath;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created by Ivan on 2015/10/27.
 */
/*

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

        Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

        For example,

        Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

        Return:
        ["AAAAACCCCC", "CCCCCAAAAA"].
*/

public class N187_RepeatedDNASequences {
    public static void test(){
        String str="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        List<String> ret=new N187_RepeatedDNASequences().findRepeatedDnaSequences(str);
        for(String s:ret){
            System.out.println(s);
        }
    }

    public List<String> findRepeatedDnaSequences(String s) {
        ArrayList<String> ret=new ArrayList<>();
        if(s==null||s.length()<10){
            return  ret;
        }

        int k=0;
        for(int i=0;i<10;++i){
            k=(k<<2)|getInt(s.charAt(i));
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(k,1);
        for(int i=10;i<s.length();++i){
            k=(k<<2)&0x0ffffc|getInt(s.charAt(i));
            if(map.containsKey(k)){
                if(map.get(k)==1){
                    ret.add(s.substring(i-9,i+1));
                    map.put(k,2);
                }
            }else{
                map.put(k,1);
            }
        }

        return ret;
    }

    private int getInt(char c){
        switch (c){
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
            default:
                return 0;
        }
    }
}
